<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>猪喝水</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
        
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        <style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="猪喝水">猪喝水</h1>
<ul>
<li>leetcode 458</li>
<li><a href="https://leetcode.com/problems/poor-pigs/">https://leetcode.com/problems/poor-pigs/</a></li>
<li><a href="https://www.zhihu.com/question/60227816/answer/1274968885">https://www.zhihu.com/question/60227816/answer/1274968885</a></li>
</ul>
<h2 id="题目描述">题目描述</h2>
<p>有 1000 只水桶，其中有且只有一桶装的含有毒药，其余装的都是水。它们从外观看起来都一样。如果小猪喝了毒药，它会在 15 分钟内死去。</p>
<p>问题来了，如果需要你在一小时内，弄清楚哪只水桶含有毒药，你最少需要多少只猪？</p>
<p>回答这个问题，并为下列的进阶问题编写一个通用算法。</p>
<p>进阶:</p>
<p>假设有 n 只水桶，猪饮水中毒后会在 m分钟内死亡，你需要多少猪（x）就能在 p分钟内找出 “有毒” 水桶？这 n 只水桶里有且仅有一只有毒的桶。</p>
<p>提示：</p>
<p>可以允许小猪同时饮用任意数量的桶中的水，并且该过程不需要时间。
小猪喝完水后，必须有 m 分钟的冷却时间。在这段时间里，只允许观察，而不允许继续饮水。
任何给定的桶都可以无限次采样（无限数量的猪）。</p>
<h2 id="解法">解法</h2>
<p>假设有n头猪， 允许喝水k次。</p>
<pre><code>能喝水k次，就代表有(k+1)种状态， 那么能探测的水桶数目就是 (k+1)^n
</code></pre>
<p>具体到本题， 就有5种状态, 可以理解为5进制数</p>
<ul>
<li>
<p>15分钟死去</p>
</li>
<li>
<p>30分钟死去</p>
</li>
<li>
<p>45分钟死去</p>
</li>
<li>
<p>60分钟死去</p>
</li>
<li>
<p>没死</p>
<pre><code>  (k+1)^n &gt;= target
  n * lg(k+1) &gt;= lg(target)
  n &gt;= lg(target) / lg(k+1)
</code></pre>
</li>
</ul>
<h2 id="如果有2头猪能覆盖25桶水">如果有2头猪，能覆盖25桶水。</h2>
<p>将每桶水编号i=0~24, 转换成5进制数Five_i 具体喝法如下。</p>
<p><img src="file:///e:\gitee\leetcode\math\pics\pig1.png" alt="pig1.png"></p>
<pre><code><code><div>第1头猪 第0分钟， 喝水来自 Five_i 第1位为0的水桶  0  5 10 15 20
第1头猪 第15分钟，喝水来自 Five_i 第1位为1的水桶  1  6 11 16 21
第1头猪 第30分钟，喝水来自 Five_i 第1位为2的水桶  2  7 12 17 22    
第1头猪 第45分钟，喝水来自 Five_i 第1位为3的水桶  3  8 13 18 23
                                               4  9 14 19 24

第2头猪 第0分钟， 喝水来自 Five_i 第2位为0的水桶  0  1  2  3  4
第2头猪 第15分钟，喝水来自 Five_i 第2位为1的水桶  5  6  7  8  9
第2头猪 第30分钟，喝水来自 Five_i 第2位为2的水桶 10 11 12 13 14
第2头猪 第45分钟，喝水来自 Five_i 第2位为3的水桶 15 16 17 18 19
                                              20 21 22 23 24
</div></code></code></pre>
<p>而第几分钟死代表当前位数的权重，15分钟死表示权重是1，30分钟死表示权重是2，45分钟死表示权重是3 ，60分钟死表示权重是4，60分钟依然活着表示权重是0。</p>
<p>如果第1头猪在第30分钟死去， 第二头猪在45分钟死去， 那么对应的水桶变化就是 2 * 5^0 + 3 * 5^1 = 17</p>
<h2 id="如果有5头猪能覆盖-55--3125-桶水">如果有5头猪，能覆盖 5^5 = 3125 桶水</h2>
<p>一样的喝法</p>
<p>如果1号猪第30分钟死了，2号猪第15分钟死了，3号猪第45分钟死了，4，5号都活到了最后。则毒水对应的5进制编码是</p>
<p>0* 5^4 + 0<em>5^3 + 3</em>5^2 + 1<em>5^1 + 2</em>5^0 = 82</p>
<p>也就是第82桶水有毒。</p>

    </body>
    </html>